A popular form of computer graphics is the so-called "wire-frame model" type. Any curved surfaces of three-dimensional objects are approximated by a plurality of flat surfaces. Then all surface boundaries that are not straight-line in nature are approximated by straight lines. The end points of the straight lines are designated "nodes", are assigned node numbers and are listed in memory according to their assigned numbers. Each listing in memory includes the spatial coordinates of the node and further includes descriptions of the topological relationship of that node to other nodes as identified by their assigned node numbers. The spatial coordinates are normally specified in terms of three-dimensional Cartesian coordinates x, y, and z. This listing in memory is considered to describe "graphics primitives." These primitives are basic geometric shapes and as here considered are polygons.
Rotation, precession and translation of three-dimensional objects as viewed on the display screen of the television terminal involves geometric processing of the stored memory listings, which is done in the central processing unit of the computer. The modified listings are then furnished to a drawing processor, which converts the listings to a full raster of image samples for storage in computer memory. This full raster of image samples is then supplied to a display processor that responds to these image samples to generate video signals for the television terminal. At the present state of the art the most advanced drawing and display processors use dedicated digital hardware to provide sufficient processing capability to convert the graphics primitives to video signals at rates which allow the simulation of fluid motion of objects on the display screen of the television terminal.
The geometric processing referred to above generally involves three basic steps. In the first of these steps the spatial coordinates of the nodes are spatially transformed--i.e., moved in image space corresponding to the rotation and translation of the object described by the graphics primitives. The second of these steps, which is sometimes omitted, is the recalculation of the transformed node coordinates to take into account perspective. The third step in geometric processing is clipping, where image data outside of the field of view of the display are discarded. With the more powerful drawing and display processors currently becoming available, the time involved in the spatial transformation of node spatial coordinates becomes the most limiting factor in obtaining high-rate fluid motion of objects on the display screen of the televison terminal. Accordingly, a faster method for performing the spatial transformation of each of these nodes is sought. The invention concerns the speeding up of the first basic step in geometric processing by reducing the number of digital multiplications involved.
The mathematics used for spatial transformation in the prior art can be simply described in the following matrix algebra equation. EQU P'=AP+T
Here, P is the 3.times.1 matrix descriptive of the x, y, z coordinates of the original position of a sample of the object surface in three-dimensional image space. A is the 3.times.3 matrix descriptive of the rotation and precession of the object in three-dimensional space, assuming A to be normalized. A may be the normalized A, however, with all coefficients multiplied by a scalar factor, which changes the size of the object, as well as arranging for its rotation, precession, or both rotation and precession. T is the 3.times.1 matrix descriptive of the translation, in image space, of the center of rotation and precession of the object. P' is the 3.times.1 matrix descriptive of the transformed position of the sample in image space.
The equivalent of the matrix equation in linear algebra are the three equations following. EQU x'=ax+by+cz+d EQU y'=ex+fy+gz+h EQU z'=jx+ky+lz+m
Here, a-c, e-g and j-1 are the coefficients appearing in the A matrix; and d, h and m are the coefficients appearing in the T matrix. The original coordinates of the sample have values x, y, z and the spatially transformed coordinates of the sample have the values x', y', z'. There are nine digital multiplications (ax, by, cz, ex, fy, gz, jx, ky and lz) involved in the spatial transformation of a single sample and nine digital additions.
The inventor observes that typically many of the plane surfaces bounded by nodes in the wire frame model are parallelograms. Other surfaces with pairs of parallel, equal-length sides are also possible. When this is so, an alternative method of performing spatial transformations can be more efficient than the prior art method described above; and, when this is not so, this alternative method is no less efficient than the prior art method.